instance = {
    "real1": """12 9
3 3 1 2 2 2 3 3 2 4 4 5 5 4 6 2 7 3 8 2 9 3
3 3 1 4 2 5 3 4 2 4 3 5 4 4 6 3 7 4 8 5 9 4
3 3 1 6 2 5 3 4 2 4 4 5 2 4 6 3 7 4 8 2 9 5
3 3 1 4 2 3 3 4 2 4 6 5 5 4 6 3 7 6 8 5 9 8
3 3 1 4 2 5 3 3 2 4 3 5 1 4 6 3 7 4 8 6 9 5
3 3 1 6 2 5 3 4 2 4 2 5 3 4 6 4 7 3 8 9 9 5
3 3 1 5 2 2 3 4 2 4 4 5 6 4 6 3 7 4 8 3 9 5
3 3 1 3 2 5 3 4 2 4 7 5 5 4 6 3 7 3 8 6 9 4
3 3 1 2 2 5 3 4 2 4 1 5 2 4 6 7 7 8 8 6 9 5
3 3 1 3 2 6 3 4 2 4 3 5 4 4 6 4 7 8 8 6 9 7
3 3 1 5 2 2 3 4 2 4 3 5 5 4 6 6 7 7 8 6 9 5
3 3 1 6 2 5 3 4 2 4 5 5 4 4 6 3 7 4 8 7 9 5""",
    "real2": """12 10
4 3 1 45 2 48 3 50 3 4 35 5 35 6 30 2 7 30 8 35 2 9 25 10 26
4 3 1 45 2 50 3 45 3 4 35 5 36 6 35 2 7 35 8 34 2 9 25 10 30
4 3 1 50 2 45 3 46 3 4 35 5 36 6 36 2 7 31 8 34 2 9 30 10 31
4 3 1 50 2 48 3 48 3 4 34 5 38 6 35 2 7 32 8 33 2 9 27 10 31
4 3 1 45 2 46 3 48 3 4 30 5 35 6 50 2 7 34 8 32 2 9 28 10 31
4 3 1 45 2 45 3 45 3 4 30 5 35 6 50 2 7 33 8 32 2 9 30 10 26
4 3 1 47 2 50 3 47 3 4 31 5 30 6 35 2 7 35 8 31 2 9 29 10 25
4 3 1 50 2 45 3 48 3 4 32 5 30 6 34 2 7 34 8 30 2 9 24 10 27
4 3 1 48 2 46 3 46 3 4 33 5 34 6 30 2 7 34 8 30 2 9 25 10 25
4 3 1 45 2 47 3 47 3 4 33 5 33 6 30 2 7 35 8 34 2 9 32 10 26
4 3 1 46 2 50 3 45 3 4 34 5 30 6 50 2 7 30 8 35 2 9 31 10 25
4 3 1 48 2 50 3 47 3 4 35 5 31 6 35 2 7 32 8 30 2 9 25 10 26
""",
    "real3": """14 13
8 2 1 110 2 110 3 3 360 4 360 5 360 1 6 50 1 7 100 1 8 160 3 9 200 10 200 11 200 1 12 50 1 13 100 
8 2 1 110 2 110 3 3 360 4 360 5 360 1 6 50 1 7 100 1 8 160 3 9 200 10 200 11 200 1 12 50 1 13 100 
8 2 1 110 2 110 3 3 360 4 360 5 360 1 6 50 1 7 100 1 8 160 3 9 200 10 200 11 200 1 12 50 1 13 100 
8 2 1 120 2 120 3 3 420 4 420 5 420 1 6 50 1 7 90  1 8 170 3 9 220 10 220 11 220 1 12 70 1 13 110 
8 2 1 120 2 120 3 3 420 4 420 5 420 1 6 50 1 7 90  1 8 170 3 9 220 10 220 11 220 1 12 70 1 13 110 
8 2 1 140 2 140 3 3 350 4 350 5 350 1 6 50 1 7 120 1 8 170 3 9 150 10 150 11 150 1 12 60 1 13 140 
8 2 1 140 2 140 3 3 350 4 350 5 350 1 6 50 1 7 120 1 8 170 3 9 150 10 150 11 150 1 12 60 1 13 140 
8 2 1 140 2 140 3 3 350 4 350 5 350 1 6 50 1 7 120 1 8 170 3 9 150 10 150 11 150 1 12 60 1 13 140 
8 2 1 140 2 140 3 3 350 4 350 5 350 1 6 50 1 7 120 1 8 170 3 9 150 10 150 11 150 1 12 60 1 13 140 
8 2 1 140 2 140 3 3 380 4 380 5 380 1 6 60 1 7 110 1 8 220 3 9 240 10 240 11 240 1 12 70 1 13 160 
8 2 1 140 2 140 3 3 380 4 380 5 380 1 6 60 1 7 110 1 8 220 3 9 240 10 240 11 240 1 12 70 1 13 160 
8 2 1 140 2 140 3 3 380 4 380 5 380 1 6 60 1 7 110 1 8 220 3 9 240 10 240 11 240 1 12 70 1 13 160 
8 2 1 140 2 140 3 3 380 4 380 5 380 1 6 60 1 7 110 1 8 220 3 9 240 10 240 11 240 1 12 70 1 13 160 
8 2 1 140 2 140 3 3 380 4 380 5 380 1 6 60 1 7 110 1 8 220 3 9 240 10 240 11 240 1 12 70 1 13 160 
""",
    "real4": """10 10
5 2 1 4 2 4 2 3 5 4 5 2 5 3 6 5 2 7 1 8 3 2 9 5 10 1 
5 2 1 4 2 5 2 3 4 4 1 2 5 5 6 1 2 7 4 8 4 2 9 5 10 3 
5 2 1 4 2 1 2 3 1 4 3 2 5 4 6 1 2 7 5 8 5 2 9 4 10 4 
5 2 1 1 2 2 2 3 4 4 2 2 5 2 6 3 2 7 1 8 2 2 9 1 10 1 
5 2 1 4 2 1 2 3 3 4 3 2 5 2 6 1 2 7 2 8 3 2 9 5 10 1 
5 2 1 3 2 5 2 3 1 4 3 2 5 3 6 4 2 7 2 8 2 2 9 1 10 1 
5 2 1 2 2 1 2 3 1 4 1 2 5 3 6 4 2 7 5 8 5 2 9 5 10 3 
5 2 1 5 2 5 2 3 2 4 2 2 5 1 6 1 2 7 2 8 5 2 9 3 10 2 
5 2 1 5 2 3 2 3 2 4 4 2 5 2 6 3 2 7 1 8 3 2 9 4 10 3 
5 2 1 3 2 1 2 3 5 4 4 2 5 5 6 3 2 7 2 8 2 2 9 4 10 2 """
}

best_known = {
    "real1": 23,
    "real2": 297,
    "real3": 3570,
    "real4": 22,
}
